package com.aurora.leetcode;

import com.aurora.leetcode.entity.ListNode;
import com.aurora.leetcode.util.MyUtils;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author : Aurora
 * @date : 2024/4/29 09:50
 * @description
 * <p>给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。</p>
 *
 */
public class IntersectionNode_0207 {
    //解法一  leetcode运行时间为3ms
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pA = headA;
        ListNode pB = headB;
        List<ListNode> listA = new ArrayList<>();
        List<ListNode> listB = new ArrayList<>();
        while(pA !=null || pB!=null){
            if(pA != null){
                listA.add(pA);
                pA = pA.next;
            }
            if(pB !=null){
                listB.add(pB);
                pB = pB.next;
            }
        }
        ListNode start = null;
        for(int i=listA.size()-1,j=listB.size()-1;i>=0&&j>=0;--i,--j){
            ListNode tempA = listA.get(i);
            ListNode tempB = listB.get(j);
            if(tempA.val == tempB.val){
                start = tempA;
            }else{
                return start;
            }
        }
        return start;
    }
    //解法二：使用Hashset leetcode运行时间为9ms
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        Set<ListNode> set = new HashSet<>();
        ListNode pA = headA;
        ListNode pB = headB;
        while((pA != null) || (pB != null)){
            if(pA != null){
                boolean a = set.add(pA);
                if(!a) return pA;
                pA = pA.next;
            }
            if(pB !=null){
                boolean b = set.add(pB);
                if(!b) return pB;
                pB = pB.next;
            }
        }
        return null;
    }

    //解法三：双指针（leetcode官方）
    public ListNode getIntersectionNode3(ListNode headA, ListNode headB){
        if(headA == null || headB == null){
            return null;
        }
        ListNode pA = headA;
        ListNode pB = headB;
        while(pA != pB){
            pA = pA == null?headB: pA.next;
            pB = pB == null?headA: pB.next;
        }
        return pA;
    }



    /**
     * <p>exp1:</p>
     * <p>listA = [4,1,8,4,5], listB = [5,0,1,8,4,5]</p>
     *
     * <p>exp2</p>
     * <p>listA = [0,9,1,2,4], listB = [3,2,4]</p>
     */

    public static void main(String[] args) {
/*        int[] a = new int[]{4,1,8,4,5};
        int[] b = new int[]{5,0,1,8,4,5};*/
//        int[] a = new int[]{0,9,1,2,4};
//        int[] b = new int[]{3,2,4};
//        ListNode listNodeA = MyUtils.constructListNode(a);
//        ListNode listNodeB = MyUtils.constructListNode(b);
//        IntersectionNode_0207 obj = new IntersectionNode_0207();
//        ListNode startNode = obj.getIntersectionNode2(listNodeA, listNodeB);
//        System.out.println(startNode.val);
        System.out.println(null == null);
    }

}
